import java.util.Arrays;

/**
 * 自底向上归并排序
 */
public enum BUSort implements Sort {
    INSTANCE;


    public <E extends Comparable<E>> void sort(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);
        int n = arr.length;
        //遍历和并的区间长度，只要合并的区间长度还没有达到n，就需要继续合并

        for (int sz = 1; sz < n; sz += sz) {
            //遍历合并的两个区间的起始位置i,合并[i,i+sz-1]和[i+sz, Math.min(i + sz + sz - 1, n - 1)]

            for (int i = 0; i + sz < n; i += sz + sz)
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), temp);
        }
    }


    /**
     * 一旦把递归函数的宏观语义定义下来之后，就完全可以把这个递归函数本身看成是另外一个函数
     * 这个函数可以做一些事情，并不需要把递归函数想象的那么特殊
     *
     * @param arr
     * @param l
     * @param r
     * @优化思路 1： 如果arr[mid]< arr[mid+1] 则表示arr已经有序了
     * @优化思路(使用插入排序法优化) 2： 如果数据规模比较小，在16个之间，就不使用归并排序法，而是使用插入排序法
     */
    private <E extends Comparable<E>> void sort(E[] arr, int l, int r, E[] temp) {

        if (l >= r) return; //求解最基本的问题
//        if (r - l <= 15) {
//            insertionSort(arr, l, r);
//            return;
//        }
//        int mid = (l + r) / 2; //有可能整型溢出
        int mid = l + (r - l) / 2;
        //对arr[l,mid]进行排序
        sort(arr, l, mid, temp);//把原问题转化成更小的问题
        //对arr[mid+1,r]进行排序
        sort(arr, mid + 1, r, temp);
        //对arr[l,mid]和arr[mid+1,r]
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, l, mid, r, temp);
        }
    }

    /**
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    public <E extends Comparable<E>> void insertionSort(E[] arr, int l, int r) {
        for (int i = l; l <= r; l++) {
            E t = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;

        }
    }

    /**
     * @param arr
     * @param l
     * @param mid
     * @param r
     * @param <E>
     * @Desc 合并两个有序的区间 arr[l..mid] 和 arr[mid+1,r]
     * @ 优化思路3 : 对于链表来说，数据规模变大的时候，性能反而变低了，因为在链表中操作要不停的new node节点，下面这个函数也是一样的
     */
    private <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {


        System.arraycopy(arr, l, temp, l, r - l + 1);
        int i = l, j = mid + 1;

        //每轮为arr[k]进行赋值
        for (int k = l; k <= r; k++) {
            //arr[i]和arr[j],在取出这两个索引之前要判断这两个索引有没有越界
            if (i > mid) {
                arr[k] = temp[j];
                j++;
            } else if (j > r) {
                arr[k] = temp[i];
                i++;
            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i];
                i++;
            } else {

                arr[k] = temp[j];
                j++;
            }
        }

    }
    public int reversePairs(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) res++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Integer arr[] = new Integer[]{2, 6, 8, 7, 4, 3, 5, 1};
        int[] arr2 = new int[]{2, 6, 8, 7, 4, 3, 5, 1};

        MergeSort3 mergeSort = MergeSort3.INSTANCE;
        mergeSort.printArr(arr);
        mergeSort.sort(arr);
        mergeSort.printArr(arr);
        System.out.println();
        System.out.println();
        int i = mergeSort.reversePairs(arr2);
        System.out.println(i);

    }

}
